package com.dylan.algorithm.sparsearray;

import java.util.Arrays;

/**
 * @author zhangshaojian
 * @description
 * @date 2022/4/24 16:46
 */
public class Main {
    /**
     * 稀疏数组:当传输的二维数组只有有限的实效数据时、将原二维数组的行、列、有效数个数作为首行、后续行记录有效数据所载行、列、具体数值。
     * 目的:减少数据传输消耗、以及存储空间。
     */
    public static void main(String[] args) {
        int[][] ints = initOriginalArray();
        for (int[] column : ints) {
            System.out.println(Arrays.toString(column));
        }

        System.out.println("==========================================================");
        int[][] sparse = serializeSparseArray(ints);
        for (int[] column : sparse) {
            System.out.println(Arrays.toString(column));
        }
        System.out.println("==========================================================");

        int[][] original = deserializeSparseArray(sparse);
        for (int[] column : original) {
            System.out.println(Arrays.toString(column));
        }

    }

    private static int[][] initOriginalArray() {
        int[][] ints = new int[11][11];
        ints[1][2] = 1;
        ints[2][3] = 2;
        return ints;
    }

    /**
     * 序列化稀疏数组
     *
     * @param originalArray 原数组
     * @return 稀疏数组
     */
    private static int[][] serializeSparseArray(int[][] originalArray) {

        if (originalArray == null || originalArray.length == 0) {
            throw new RuntimeException("原数组不能为空");
        }
        getCount(originalArray);
        int[][] ints = new int[getCount(originalArray) + 1][3];
        ints[0][0] = originalArray.length;
        ints[0][1] = originalArray[0].length;
        ints[0][2] = getCount(originalArray);
        int row = 0;
        for (int i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                int value = originalArray[i][j];
                if (value != 0) {
                    int index = ++row;
                    ints[index][0] = i;
                    ints[index][1] = j;
                    ints[index][2] = value;
                }
            }
        }
        return ints;
    }

    private static int getCount(int[][] originalArray) {
        long count = Arrays.stream(originalArray).flatMapToInt(Arrays::stream).filter(it -> it != 0).count();
        return (int) count;
    }

    /**
     * 反序列化稀疏数组
     *
     * @param sparseArray 稀疏数组
     * @return 原生数组
     */
    private static int[][] deserializeSparseArray(int[][] sparseArray) {
        int[][] ints = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i <= sparseArray[0][2]; i++) {
            ints[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return ints;
    }

}
